package 动态规划;

/**
 * @author: yangwk
 * @date: 2023/4/6
 * @description:
 **/
public class 最长回文子序列 {

    //最长回文子序列
    private static int LongestPalindromeSubSeq(String str) {
        int[][] dp = new int[str.length()][str.length()];
        for (int i = 0; i < dp.length; i++) {
            dp[i][i] = 1;
        }
        for (int i = str.length() - 2; i >= 0; i--) {
            for (int j = i + 1; j < str.length(); j++) {
                if (str.charAt(i) == str.charAt(j)) {
                    dp[i][j] = dp[i + 1][j - 1] + 2;
                } else {
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[0][str.length() - 1];
    }

}
